
#include <iostream>
 #include <fstream>
#include <vector>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;
#define MAX_N 201
const int INF = 1<<30;
int in[MAX_N];
int out[MAX_N];
map<int,int> edge[MAX_N];


void solve()
{
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=N;i++)
        in[i]=out[i]=0;
    in[1]=INF;

    int u,v,w;
    for(int m=1;m<=M;m++){
        cin>>u>>v>>w;
        edge[u][v]=w;
        edge[v][u]=w;

        map<int,int> route;
        vector<int> stackk;
        int mark[MAX_N];
        for(int k=0;k<MAX_N;k++)mark[k]=0;
        stackk.push_back(1);
        while(!stackk.empty()){
            int node = stackk.back();
            stackk.pop_back();
            for(map<int,int>::iterator it=edge[node].begin();it!=edge[node].end();it++)
            {
                if(mark[it->first]==0){
                    stackk.push_back(it->first);
                    mark[it->first]=1;
                    route[it->first]=node;
                }
            }
        }

        if(route[N] != 0){
            int minflow=INF;
            int cur;
            cur = N;
            while(cur!=1){
                int pre = route[cur];
                minflow = min(minflow,edge[pre][cur]);
                cur=pre;
            }
            cur = N;
            while(cur!=1){
                int pre = route[cur];
                edge[pre][cur]-=minflow;
                edge[cur][pre]-=minflow;
                if(edge[pre][cur]==0)
                    edge[pre].erase(cur);
                if(edge[cur][pre]==0)
                    edge[cur].erase(pre);

                cur=pre;
            }
            cout<<m<<" "<<minflow<<endl;
        }
    }

}
int main()
{
    int T;
    ifstream in("f:\in.txt");
    cin.rdbuf(in.rdbuf());
    cin>>T;
    for (int t = 1; t <= T; t++)
    {
        cout<<"Case #"<<t<<":"<<endl;
        solve();
    }

    return 0;
}

